/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * N叉树前序遍历顺序
 * 
 * 
 * @author zhong
 *
 */
public class NaryTreePreorderTraversal {
	class Node {
		public int val;
		public List<Node> children;

		public Node() {
		}

		public Node(int _val, List<Node> _children) {
			val = _val;
			children = _children;
		}
	}

	public List<List<Integer>> levelOrder(Node root) {
		List<List<Integer>> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			List<Integer> curLevel = new ArrayList<>();
			for (int i = 0; i < size; i++) {
				Node cur = queue.poll();
				curLevel.add(cur.val);
				queue.addAll(cur.children);
			}
			res.add(curLevel);
		}
		return res;
	}

	/**
	 * 用迭代的方式：注意栈会导致左右顺序相反，所以需要特殊处理
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> preorder(Node root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			int childSize = cur.children.size();
			for (int i = 0; i < childSize; i++) {
				stack.add(cur.children.get(childSize - i - 1));
			}
			res.add(cur.val);
		}
		return res;
	}

	/**
	 * 后序：
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> postorder(Node root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Stack<Node> stack = new Stack<>();
		Stack<Node> stack2 = new Stack<>();
		stack.push(root);
		stack2.add(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			int childSize = cur.children.size();
			for (int i = 0; i < childSize; i++) {
				stack.add(cur.children.get(childSize - i - 1));
				stack2.add(cur.children.get(childSize - i - 1));
			}
		}
		while (!stack2.isEmpty()) {
			res.add(stack2.pop().val);
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
